#include <iostream>
#include <string>
#include <vector>
using std::cout;
using std::endl;

// 堆的应用：求TopN（最大最小值/优先队列、top10、中位数、百分位）

// 练习：编码实现访问量最大的topN关键词
struct Node {
  int count;
  std::string word;
};

void Swap(Node& n1, Node& n2) {
  Node node = n1;
  n1 = n2;
  n2 = node;
}

// 小顶堆。顶元素最小，存储一堆大数
class Heap {
 public:
  Heap(int topN) : topN_(topN) {}

  void Insert(const Node& node) {
    if (vec_.size() < topN_) {
      vec_.emplace_back(node);
      HeapifyToUp(vec_.size() - 1);
    } else if (node.count > vec_[0].count) {
      vec_[0] = node;
      HeapifyToDown(0);
    }
  }

  void Print() const {
    for (auto& item : vec_) {
      cout << item.count << ':' << item.word << endl;
    }
  }

 private:
  int ParentIdx(int idx) const { return (idx + 1) / 2 - 1; }
  int LeftChildIdx(int idx) const { return (idx + 1) * 2 - 1; }
  int RightChildIdx(int idx) const { return (idx + 1) * 2 + 1 - 1; }
  bool IsRoot(int idx) const { return idx <= 0; }
  bool IsLeaf(int idx) const { return idx >= vec_.size() / 2; }
  bool InRange(int idx) const { return idx < vec_.size(); }

  void HeapifyToUp(int idx) {
    while (!IsRoot(idx)) {
      int parent = ParentIdx(idx);
      if (vec_[parent].count > vec_[idx].count) {
        Swap(vec_[parent], vec_[idx]);
        idx = parent;
      } else {
        break;
      }
    }
  }
  void HeapifyToDown(int idx) {
    while (InRange(idx)) {
      int child = idx;
      int left = LeftChildIdx(idx);
      if (InRange(left)) {
        if (vec_[left].count < vec_[idx].count) child = left;
      }
      int right = RightChildIdx(idx);
      if (InRange(right)) {
        if (vec_[right].count < vec_[idx].count &&
            vec_[right].count < vec_[left].count)
          child = right;
      }
      if (child == idx) break;
      Swap(vec_[child], vec_[idx]);
      idx = child;
    }
  }

  std::vector<Node> vec_;
  int topN_;
};

void TestHeap() {
  // 先用map统计出来每个词的个数，再利用堆取topN
  Heap heap(3);
  heap.Insert({2, "222"});
  heap.Insert({4, "444"});
  heap.Insert({3, "333"});
  heap.Insert({5, "555"});
  heap.Insert({8, "888"});
  heap.Insert({7, "777"});
  heap.Insert({1, "111"});
  heap.Insert({6, "666"});

  heap.Print();
}

int main() { TestHeap(); }